\documentclass[12pt,a4paper,french]{article} \usepackage[francais]{babel} \usepackage[utf8]{inputenc} \usepackage{a4} \usepackage{amsmath} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{framed} \usepackage[amsmath,thmmarks,thref,framed]{ntheorem} \usepackage[dvips]{graphics} \usepackage{epsfig} \usepackage{calc} \usepackage{tabls} \usepackage{slashbox} \usepackage{times} \usepackage{tabularx} \usepackage{textcomp} \usepackage{pst-all} \usepackage[a4paper]{geometry} \input{symboles.sty} \geometry{hmargin=1cm, vmargin=1.5cm} \title{ Département d'informatique \\ Partiel de mathématiques discrètes\\ Semestre 1 (Novembre 09)\\ } \date{} \begin{document} \maketitle \noindent Seule une fiche manuscrite de format A5 est autorisée. \noindent\begin{tabular}{ll} Nom: &.............................. \\ Prénom: &.............................. \end{tabular} \section{QCM} Cette partie contient 60 affirmations. Vous aurez +1 à chaque valeur de vérité trouvée, -1 à chaque erreur (et 0 en absence de réponse). Les notes seront ajustées à l'intervalle $[0;20]$ (les notes négatives auront 0).\\ Q. 1. $\pi$ est rationnel. L'assertion proposée est vraie ou fausse ?\\ Q. 2. Soit $A =\{\{a,b\},\{c\},\{d,e,f\}\}$. $a \in A$. L'assertion proposée est vraie ou fausse ?\\ Q. 3. L'intersection entre deux ensembles est l'ensemble des éléments appartenant aux deux ensembles. L'assertion proposée est vraie ou fausse ?\\ Q. 4. Soit $A =\{\{a,b\},\{c\},\{d,e,f\}\}$. $\{d,e,f\} \in A$. L'assertion proposée est vraie ou fausse ?\\ Q. 5. L'intersection de deux ensembles est l'ensemble des éléments appartenant à au moins un des deux ensembles. L'assertion proposée est vraie ou fausse ?\\ Q. 6. Le complémentaire de l'ensemble des entiers positifs ou nuls dans $\N$ est égal à l'ensemble des entiers strictement négatifs.L'assertion proposée est vraie ou fausse ?\\ Q. 7. Soit $t_1$ et $t_2$ deux termes exprimés dans une algèbre de Boole munie des opérateurs classiques +, .et $\overline{ }$. Si $t_1 . t_2 = 0$ alors $t_1 = \overline{t_2}$. L'assertion proposée est vraie ou fausse ? \\ Q. 8. Soit $t_1$ et $t_2$ deux termes exprimés dans une algèbre de Boole munie des opérateurs classiques +, .et $\overline{ }$. Si $t_1 . t_2 = 0$ alors $t_1$ ou $t_2$ sont nuls. L'assertion proposée est vraie ou fausse ? \\ Q. 9. Soit $A =\{\{a,b\},\{c\},\{d,e,f\}\}$. $P(A)$ contient 8 éléments. L'assertion proposée est vraie ou fausse ?\\ Q. 10. Le complémentaire de $A$ dans $E$ est l'ensembles des éléments de $E$ qui ne sont pas dans $A$. L'assertion proposée est vraie ou fausse ?\\ Q. 11. Par convention, $\varnothing$ a 0 élément. L'assertion proposée est vraie ou fausse ?\\ Q. 12. Soit $A =\{\{a,b\},\{c\},\{d,e,f\}\}$. $\{d,e,f\} \in A$. L'assertion proposée est vraie ou fausse ?\\ Q. 13. Le cardinal d'un ensemble fini est son nombre d'éléments. L'assertion proposée est vraie ou fausse ?\\ Q. 14. Il existe un unique ensemble vide.L'assertion proposée est vraie ou fausse ?\\ Q. 15. On considère 4 variables booléennes $a$, $b$, $c$ et $d$. Le + est le symbole du OU logique non exclusif et le . est le symbole du ET logique. L'égalité $\overline{a}.b.\overline{c}.\overline{d} = 1$ si et seulement si $a+\overline{b} + c+ d =0$. L'assertion proposée est vraie ou fausse ?\\ Q. 16. Soit $A =\{\{a,b\},\{c\},\{d,e,f\}\}$. $P(A)$ contient 3 éléments. L'assertion proposée est vraie ou fausse ?\\ Q. 17. Le complémentaire de $A$ dans $E$ est l'ensembles des éléments de $E$ qui ne sont pas dans $A$.L'assertion proposée est vraie ou fausse ?\\ Q. 18. Le complémentaire des entiers pairs dans $\N$ est égal à l'ensemble des entiers impairs.L'assertion proposée est vraie ou fausse ?\\ Q. 19. $\pi$ est irrationnel. L'assertion proposée est vraie ou fausse ?\\ Q. 20. Soit $A =\{\{a,b\},\{c\},\{d,e,f\}\}$. $ \{c \} \subset A$. L'assertion proposée est vraie ou fausse ?\\ Q. 21. On considère 4 variables booléennes $a$, $b$, $c$ et $d$. Le + est le symbole du OU logique non exclusif et le . est le symbole du ET logique. L'expression $\overline{a} + \overline{b} + c + d $ vaut 1 si et seulement $a.b$ vaut 0. L'assertion proposée est vraie ou fausse ?\\ Q. 22. Soit $A =\{\{a,b\},\{c\},\{d,e,f\}\}$. $P(A)$ contient 4 éléments.L'assertion proposée est vraie ou fausse ?\\ Q. 23. Le complémentaire de $A$ dans $E$ est l'ensemble des éléments de $A$ qui ne sont pas dans $E$.L'assertion proposée est vraie ou fausse ?\\ Q. 24. $\N$ est un ensemble infini.L'assertion proposée est vraie ou fausse ?\\ Q. 25. Soit $A =\{\{a,b\},\{c\},\{d,e,f\}\}$. $\emptyset \subset A$.L'assertion proposée est vraie ou fausse ?\\ Q. 26. $\sin(1)$ est irrationnel.L'assertion proposée est vraie ou fausse ?\\ Q. 27. Soit $A =\{\{a,b\},\{c\},\{d,e,f\}\}$. $\emptyset \in A$. L'assertion proposée est vraie ou fausse ?\\ Q. 28. $\Z$ est un ensemble infini. L'assertion proposée est vraie ou fausse ?\\ Q. 29. On considère 4 variables booléennes $a$, $b$, $c$ et $d$. Le + est le symbole du OU logique non exclusif et le . est le symbole du ET logique. L'expression $a+ \overline{b} + \overline{a}.b + \overline{c}$ est équivalent à $\overline{c} + 1$. L'assertion proposée est vraie ou fausse ?\\ Q. 30. $\Z$ est un ensemble infini.L'assertion proposée est vraie ou fausse ?\\ Q. 31. $A \cup B$ est la réunion de $A$ et de $B$. L'assertion proposée est vraie ou fausse ?\\ Q. 32. On considère 4 variables booléennes $a$, $b$, $c$ et $d$. Le + est le symbole du OU logique non exclusif et le . est le symbole du ET logique. L'égalité $a+\overline{b}+\overline{c}+\overline{d}=0$ est établie si et seulement si $a$ est la seule variable valant 0. L'assertion proposée est vraie ou fausse ?\\ Q. 33. Le complémentaire de $A$ dans $E$ est l'ensemble des éléments de $A$ qui ne sont pas dans $E$. L'assertion proposée est vraie ou fausse ?\\ Q. 34. $A \cap B$ est la réunion de $A$ et de $B$.L'assertion proposée est vraie ou fausse ?\\ Q. 35. $e$ est irrationnel. L'assertion proposée est vraie ou fausse ?\\ Q. 36. On considère 4 variables booléennes $a$, $b$, $c$ et $d$. Le + est le symbole du OU logique non exclusif et le . est le symbole du ET logique. L'expression $\overline{a}.b + a.\overline{b}$ est vraie quand $a$ et $b$ sont différents. L'assertion proposée est vraie ou fausse ?\\ Q. 37. La réunion entre deux ensembles est l'ensemble des éléments appartenant aux deux ensembles. L'assertion proposée est vraie ou fausse ?\\ Q. 38. Soit $A =\{\{a,b\},\{c\},\{d,e,f\}\}$. $\emptyset \in A$.L'assertion proposée est vraie ou fausse ?\\ Q. 39. On considère 4 variables booléennes $a$, $b$, $c$ et $d$. Le + est le symbole du OU logique non exclusif et le . est le symbole du ET logique. L'expression $\overline{a} + \overline{b} + c + d $ vaut 1 si et seulement $c.d$ vaut 1. L'assertion proposée est vraie ou fausse ?\\ Q. 40. $A \cap B$ est la réunion de $A$ et de $B$. L'assertion proposée est vraie ou fausse ?\\ Q. 41. L'intersection de deux ensembles $A$ et $B$ est l'ensemble des éléments appartenant à $A$ ou à $B$. L'assertion proposée est vraie ou fausse ?\\ Q. 42. $\pi$ est irrationnel.L'assertion proposée est vraie ou fausse ?\\ Q. 43. Soit $A =\{\{a,b\},\{c\},\{d,e,f\}\}$. $P(A)$ contient 3 éléments.L'assertion proposée est vraie ou fausse ?\\ Q. 44. Dans une algèbre de Boole munie des opérateurs classiques +, .et $\overline{ }$, on considère l'expression $E=\overline{a}(a+b)(a+c)(a+d)(a+e)$. La version la plus réduite de $E$ est 1 L'assertion proposée est vraie ou fausse ? \\ Q. 45. Dans une algèbre de Boole munie des opérateurs classiques +, .et $\overline{ }$, on considère l'expression $E=\overline{a}.b + a.c + \overline{b}.c + \overline{c}$. La version la plus réduite de $E$ est 1 L'assertion proposée est vraie ou fausse ? \\ Q. 46. Soit $A =\{\{a,b\},\{c\},\{d,e,f\}\}$. $\{\{a,b\}\} \subset A$. L'assertion proposée est vraie ou fausse ?\\ Q. 47. $\sin(1)$ est rationnel.L'assertion proposée est vraie ou fausse ?\\ Q. 48. $A \cup B$ est l'intersection de $A$ et de $B$. L'assertion proposée est vraie ou fausse ?\\ Q. 49. Soit $A =\{\{a,b\},\{c\},\{d,e,f\}\}$. $P(A)$ contient 64 éléments. L'assertion proposée est vraie ou fausse ?\\ Q. 50. $A \cap B$ est l'intersection de $A$ et $B$. L'assertion proposée est vraie ou fausse ?\\ Q. 51. $\sin(1)$ est rationnel. L'assertion proposée est vraie ou fausse ?\\ Q. 52. Le complémentaire de l'ensemble des entiers positifs ou nuls dans $\N$ est égal à l'ensemble des entiers strictement négatifs. L'assertion proposée est vraie ou fausse ?\\ Q. 53. Dans une algèbre de Boole munie des opérateurs classiques +, .et $\overline{ }$, on considère l'expression $E=\overline{a}.b + a.c + \overline{b}.c + \overline{c}$. La version la plus réduite de $E$ est 0 L'assertion proposée est vraie ou fausse ? \\ Q. 54. $A \cup B$ est la réunion de $A$ et de $B$.L'assertion proposée est vraie ou fausse ?\\ Q. 55. On considère 4 variables booléennes $a$, $b$, $c$ et $d$. Le + est le symbole du OU logique non exclusif et le . est le symbole du ET logique. L'égalité $a+\overline{b}+\overline{c}+\overline{d}=0$ est établie si et seulement si $a$ est la seule variable valant 0. L'assertion proposée est vraie ou fausse ?\\ Q. 56. $A \cap B$ est l'intersection de $A$ et $B$.L'assertion proposée est vraie ou fausse ?\\ Q. 57. Le complémentaire des entiers pairs dans $\N$ est égal à l'ensemble des entiers impairs. L'assertion proposée est vraie ou fausse ?\\ Q. 58. La réunion de deux ensembles $A$ et $B$ est l'ensemble des éléments appartenant à $A$ et à $B$. L'assertion proposée est vraie ou fausse ?\\ Q. 59. Soit $A =\{\{a,b\},\{c\},\{d,e,f\}\}$. $a \in A$. L'assertion proposée est vraie ou fausse ?\\ Q. 60. La réunion de deux ensembles $A$ et $B$ est l'ensemble des éléments appartenant à $A$ ou à $B$. L'assertion proposée est vraie ou fausse ?\\ \begin{center} \begin{tabular}{|l|c|c||l|c|c||l|c|c|} \hline Numéro & V & F & Numéro & V & F & Numéro & V & F \\ \hline Q. 1 & & & Q. 2 & & & Q. 3 & & \\ \hline Q. 4 & & & Q. 5 & & & Q. 6 & & \\ \hline Q. 7 & & & Q. 8 & & & Q. 9 & & \\ \hline Q. 10 & & & Q. 11 & & & Q. 12 & & \\ \hline Q. 13 & & & Q. 14 & & & Q. 15 & & \\ \hline Q. 16 & & & Q. 17 & & & Q. 18 & & \\ \hline Q. 19 & & & Q. 20 & & & Q. 21 & & \\ \hline Q. 22 & & & Q. 23 & & & Q. 24 & & \\ \hline Q. 25 & & & Q. 26 & & & Q. 27 & & \\ \hline Q. 28 & & & Q. 29 & & & Q. 30 & & \\ \hline Q. 31 & & & Q. 32 & & & Q. 33 & & \\ \hline Q. 34 & & & Q. 35 & & & Q. 36 & & \\ \hline Q. 37 & & & Q. 38 & & & Q. 39 & & \\ \hline Q. 40 & & & Q. 41 & & & Q. 42 & & \\ \hline Q. 43 & & & Q. 44 & & & Q. 45 & & \\ \hline Q. 46 & & & Q. 47 & & & Q. 48 & & \\ \hline Q. 49 & & & Q. 50 & & & Q. 51 & & \\ \hline Q. 52 & & & Q. 53 & & & Q. 54 & & \\ \hline Q. 55 & & & Q. 56 & & & Q. 57 & & \\ \hline Q. 58 & & & Q. 59 & & & Q. 60 & & \\ \hline \end{tabular} \end{center} %\end{huge} \section{Problèmes} \subsection{Théorie des ensembles} Rappel: pour deux ensembles $A$ et $B$, on appelle \emph{différence symétrique}, noté $A\Delta B$, l'ensemble défini par \[ A \Delta B = (A \cup B) \setminus (A \cap B) \] c'est-à-dire que $A \Delta B$ est constitué des éléments qui appartiennent soit à $A$, soit à $B$, mais pas aux deux. Soit $A$, $B$ et $C$ trois ensembles. \begin{enumerate} \item Montrer que l'opérateur est commutatif. \item Montrer que l'opérateur possède un élément neutre que l'on explicitera. \item Montrer que si $A \Delta B = A \Delta C$ alors $B = C$. \end{enumerate} \subsection{Algèbre de Boole 1} A l'aide des méthodes de votre choix (Karnaugh ou consensus), réécrire les expression suivantes en une somme qui contient le moins de monomes possibles. \begin{enumerate} \item $A =\overline{c}\overline{d}b + cab + \overline{c}dab + c\overline{d}\overline{a}b + ca\overline{b}$. % ac + ab + b\overline{d} \item $B = \overline{a}b\overline{c}\overline{d}+ ab\overline{c} + a\overline{b}\overline{c}d + acd + abc\overline{d} + \overline{a}\overline{b}d$ % \overline{a}b\overline{c}\overline{d} + ab + \overline{b}d \end{enumerate} \subsection{Algèbre de Boole 2} On considère le jeu avec une équipe de quatre candidats dont un chef d'équipe. Chaque candidat dispose d'un boitier lui permettant de donner un vote de type oui/non. Un affichage central présente l'avis de la majorité des candidats. Lorsqu'il y a le même nombre de votes \og oui\fg{} que de vôtes \og non\fg{} le vote du chef d'equipe est prépondérant. \begin{enumerate} \item Construire la table de vérité du système central d'affichage; \item Exprimez l'affichage centrale en FCD; \item Formez une expression booléenne minimale de l'affichage. \end{enumerate} \end{document}